﻿#pragma once

//------------------------------------------------------------

template<class TElem>
void quickSort(TElem v[], int num)
{
	// Pre: v tiene al menos num elementos y
	// num >= 0
	quickSort(v, 0, num-1);
	// Post: se han ordenado las num primeras posiciones de v
}

//------------------------------------------------------------

template<class TElem>
void quickSort(TElem v[], int a, int b)
{
	// Pre: 0 <= a <= num && -1 <= b <= num-1 && a <= b+1
	int p;
	if ( a <= b ) 
	{
		particionR(v, a, b, p);
		quickSort(v, a, p-1);
		quickSort(v, p+1, b);
	}
	// Post: v está ordenado entre a y b
}

//------------------------------------------------------------

template<class TElem>
void particion (TElem v[], int a, int b, int & p)
{
	// Pre: 0 <= a <= b <= num-1
	int i, j;
	TElem aux;
	i = a+1;
	j = b;
	while ( i <= j ) 
	{
		if ( (v[i] > v[a]) && (v[j] < v[a]) ) 
		{
			aux = v[i]; 
			v[i] = v[j]; 
			v[j] = aux;
			i = i + 1; 
			j = j - 1;
		}
		else 
		{
			if ( v[i] <= v[a] ) 
				i = i + 1;
			if ( v[j] >= v[a] ) 
				j = j - 1;
		}
	}
	p = j;
	aux = v[a]; 
	v[a] = v[p]; 
	v[p] = aux;
	// Post: 0 <= a <= p <= b <= num-1 y
	// todos los elementos desde 'a' hasta 'p-1' son <= v[p] y
	// todos los elementos desde 'p+1' hasta 'b' son <= v[p] <- error? > v[p]
}

//------------------------------------------------------------
// Ejercicio propuesto: Partición en recursivo.
//------------------------------------------------------------

template<class TElem>
void particionR(TElem v[], int a, int b, int&p)
{
	// Pre: 0 <= a <= b <= num-1
	int i = a+1;
	int j = b;
	p = particionRAux(v,a,i,j);
	// Post: 0 <= a <= p <= b <= num-1 y
	// todos los elementos desde 'a' hasta 'p-1' son <= v[p] y
	// todos los elementos desde 'p+1' hasta 'b' son > v[p]
}

// Ok, funciona, faltan los pasos.
template<class TElem>
int particionRAux(TElem v[], int a, int i, int j)
{
	// Pre: (0 <= a < i) && (0 <= j <= n-1) && (i <= j+1)
	TElem aux;
	int p; 
	if(i == j+1) // Equivale a (i > j)
	{
		p = j;
		aux = v[a];
		v[a] = v[p];
		v[p] = aux;
	}
	else if(i <= j)
	{
		if((v[i] > v[a]) && (v[j] < v[a]))
		{
			aux = v[i]; 
			v[i] = v[j]; 
			v[j] = aux;
			i++;
			j--;
		}
		else
		{
			if ( v[i] <= v[a] ) 
				i = i + 1;
			if ( v[j] > v[a] ) 
				j = j - 1;
		}
		p = particionRAux(v,a,i,j);
	}
	return p;
}

template<class TElem>
void particionRAux2(TElem v[], int a, int b, int i, int j, int&p)
{
	TElem aux;

	if(i == j+1) // Equivale a (i > j)
	{
		p = j;
		aux = v[a];
		v[a] = v[p];
		v[p] = aux;
	}
	else if(i <= j)
	{
		if((v[i] >= v[a]) && (v[j] >= v[a]))
			i++;
		if((v[i] > v[a]) && (v[j] >= v[a]) )
			j--;
		particionRAux2(v,a,b,i,j,p);
	}
}